import heapq
import collections


class Solution(object):
    def minCostToSupplyWater(self, n, wells, pipes):
        """
        :type n: int
        :type wells: List[int]
        :type pipes: List[List[int]]
        :rtype: int
        """
        visited = [0] * n
        count = 0
        stack = [(wells[i], i) for i in range(n)]
        edges = collections.defaultdict(dict)
        total = 0
        for x,y,z in pipes:
            if y - 1 in edges[x - 1]:
                edges[x - 1][y - 1] = min(edges[x - 1][y - 1], z)
            else:
                edges[x - 1][y - 1] = z
            if x - 1 in edges[y - 1]:
                edges[y - 1][x - 1] = min(edges[y - 1][x - 1], z)
            else:
                edges[y - 1][x - 1] = z
        heapq.heapify(stack)
        while count < n:
            node = heapq.heappop(stack)
            if visited[node[1]] == 0:
                visited[node[1]] = 1
                count += 1
                total += node[0]
                for item in edges[node[1]]:
                    if visited[item] == 0:
                        heapq.heappush(stack, (edges[node[1]][item], item))
        return total


data = Solution()
# n = 3
# wells = [1, 2, 2]
# pipes = [[1, 2, 1], [2, 3, 9]]
# print(data.minCostToSupplyWater(n, wells, pipes))
# n = 2
# wells = [1, 1]
# pipes = [[1, 2, 1]]
# print(data.minCostToSupplyWater(n, wells, pipes))
n = 60
wells = [91583, 30644, 78052, 35866, 15897, 55437, 90057, 56376, 46543, 32353, 71054, 42913, 26401, 43947, 27923, 38851, 14834,
 58577, 39343, 65259, 41656, 37046, 95887, 1686, 57336, 45894, 65006, 55535, 74663, 37223, 80227, 60559, 26622, 48741,
 63306, 14554, 46852, 3380, 8350, 77189, 27426, 65228, 39259, 72383, 22325, 57616, 73416, 81179, 42862, 62995, 32266,
 31435, 33693, 62021, 63511, 99532, 36944, 94214, 41914, 41937]
pipes = [[2, 1, 14339], [3, 1, 69880], [4, 2, 20701], [5, 1, 76350], [6, 5, 25976], [7, 4, 37901], [8, 5, 72080], [9, 4, 58168],
 [10, 7, 83487], [11, 3, 8257], [12, 3, 34792], [13, 3, 85560], [14, 9, 68966], [15, 10, 84714], [16, 1, 76289],
 [17, 16, 19686], [18, 15, 64769], [19, 11, 58805], [20, 19, 56495], [21, 7, 27402], [22, 15, 96447], [23, 7, 1129],
 [24, 14, 23625], [25, 5, 87392], [26, 17, 88148], [27, 23, 2848], [28, 20, 93310], [29, 19, 54942], [30, 24, 89429],
 [31, 21, 17738], [32, 22, 5512], [33, 10, 94598], [34, 7, 10143], [35, 23, 73324], [36, 30, 42883], [37, 32, 1065],
 [38, 35, 80093], [39, 11, 90180], [40, 33, 75306], [41, 9, 27672], [42, 37, 26846], [43, 32, 26995], [44, 30, 65443],
 [45, 30, 72535], [46, 17, 88157], [47, 28, 93430], [48, 33, 54406], [49, 40, 26588], [50, 2, 66704], [51, 37, 1728],
 [52, 9, 74691], [53, 32, 46125], [54, 17, 90802], [55, 39, 88735], [56, 14, 98637], [57, 40, 25363], [58, 54, 62330],
 [59, 28, 33835], [60, 12, 93612], [35, 36, 68802], [47, 59, 60189], [12, 28, 66078], [2, 5, 49615], [21, 55, 29813],
 [34, 44, 76560], [14, 29, 65002], [14, 25, 56715], [58, 59, 90169], [19, 38, 63872], [2, 13, 26225], [21, 38, 93503],
 [20, 42, 24851], [13, 27, 18869], [9, 15, 10911], [6, 9, 95709], [27, 33, 11425], [39, 52, 81471], [42, 50, 94723],
 [18, 38, 14553], [48, 52, 34348], [10, 30, 4150], [2, 46, 39087], [44, 55, 70532], [11, 52, 93928], [34, 60, 20413],
 [31, 33, 80064], [5, 11, 1947], [28, 34, 56143], [19, 25, 80577], [10, 54, 20622], [24, 53, 42033], [51, 54, 36006],
 [28, 29, 46919], [31, 59, 91804], [27, 31, 41678], [12, 48, 35163], [55, 60, 58281], [33, 34, 58251], [16, 31, 51651],
 [16, 54, 73990], [15, 31, 10897], [4, 38, 42884], [1, 53, 68329], [12, 45, 78335], [33, 42, 62952], [1, 24, 8436],
 [7, 60, 81152], [9, 23, 76704], [6, 19, 42910], [14, 59, 91948], [4, 31, 30280], [13, 58, 22786], [2, 7, 23331],
 [11, 32, 30717], [5, 6, 48399], [15, 34, 27310], [47, 48, 17758], [11, 55, 83889], [10, 15, 84761], [8, 18, 66694],
 [51, 59, 39384], [17, 36, 19313], [18, 29, 40738], [14, 60, 1793], [38, 42, 26650], [1, 30, 15461], [38, 49, 91408],
 [11, 15, 10996], [41, 51, 32095], [17, 44, 5330], [41, 58, 91698], [9, 56, 19116], [49, 56, 76779], [15, 21, 80090],
 [4, 10, 99000], [21, 46, 11483], [36, 56, 82951], [20, 57, 71595], [14, 18, 71629], [3, 27, 66908], [26, 41, 26799],
 [48, 58, 91084], [4, 25, 45252], [9, 60, 29718], [29, 31, 67068], [9, 17, 90990], [8, 52, 74496], [34, 39, 7869],
 [4, 33, 84297], [6, 23, 70360], [45, 47, 55047], [7, 41, 1106], [17, 23, 27668], [27, 52, 22280], [22, 41, 41845],
 [39, 45, 61485], [45, 53, 99470], [41, 48, 59268], [39, 48, 83069], [13, 60, 70711], [28, 54, 87075], [21, 34, 10642],
 [35, 54, 1839], [3, 47, 31311], [8, 17, 86597], [30, 59, 30710], [5, 24, 25931], [12, 22, 83847], [32, 56, 90057],
 [26, 50, 83596], [26, 58, 7097], [28, 50, 29887], [21, 51, 54484], [36, 44, 23274], [24, 56, 99903], [13, 18, 15648],
 [29, 33, 61060], [24, 47, 36354], [28, 56, 69452], [40, 41, 34363], [10, 33, 34476], [5, 39, 51833], [16, 51, 67584],
 [51, 58, 90121], [51, 53, 90795], [20, 49, 61835], [25, 60, 43570], [9, 52, 39233], [11, 16, 80352], [4, 55, 91107],
 [42, 43, 82442], [1, 43, 13120], [47, 60, 5987], [5, 23, 35230], [4, 45, 23846], [4, 35, 3690], [4, 30, 72713],
 [15, 22, 35097], [8, 48, 88633], [43, 55, 5373], [21, 31, 36348], [1, 31, 39483], [5, 13, 71366], [5, 12, 88990],
 [19, 31, 61081], [27, 57, 99776], [17, 43, 84552], [4, 27, 80573], [15, 49, 38929], [15, 45, 93758], [20, 55, 63430],
 [3, 18, 40167], [19, 30, 45581], [21, 60, 66576], [6, 46, 58707], [17, 60, 87044], [4, 40, 8631], [16, 53, 83189],
 [9, 28, 16313], [46, 49, 83363], [16, 60, 22659], [22, 59, 22620], [4, 19, 72942], [13, 31, 87583], [1, 57, 13408],
 [35, 40, 36351], [1, 59, 38927], [9, 32, 62300], [35, 39, 21368], [18, 55, 58791], [9, 16, 46327], [25, 44, 47624],
 [23, 54, 8832], [43, 56, 69341], [32, 44, 23351], [25, 41, 34480], [40, 42, 25372], [3, 41, 4371], [13, 46, 74107],
 [41, 50, 82994], [14, 33, 5536], [29, 37, 73494], [37, 48, 42222], [55, 59, 52458], [15, 53, 45090], [9, 45, 13700],
 [11, 30, 69447], [43, 48, 92188], [10, 39, 33938], [23, 47, 28493], [32, 48, 40155], [1, 23, 66328], [10, 34, 66709],
 [1, 9, 57650], [7, 8, 60422], [40, 59, 61006], [23, 44, 33495], [21, 32, 36204], [4, 51, 23197], [21, 47, 71352],
 [48, 53, 51319], [25, 40, 6484], [35, 49, 30584], [34, 35, 56878], [23, 25, 20654], [18, 40, 96774], [6, 27, 67786],
 [9, 19, 35510], [23, 58, 50836], [22, 24, 41444], [17, 18, 59656], [2, 58, 62413], [5, 25, 41148], [7, 42, 59095],
 [12, 25, 3999], [26, 59, 91642], [16, 24, 39736], [8, 10, 1923], [16, 59, 8130], [50, 56, 78207], [13, 21, 91397],
 [14, 35, 23048], [14, 21, 69111], [12, 39, 32060], [36, 60, 38348], [3, 59, 57402], [32, 43, 18138], [5, 20, 69899],
 [1, 21, 94607], [24, 48, 22689], [1, 25, 31035], [7, 49, 86944], [15, 38, 65007], [29, 39, 11866], [40, 46, 96402],
 [1, 19, 30005], [36, 47, 60115], [49, 51, 92218], [49, 57, 61639], [2, 28, 94337], [53, 55, 69077], [22, 58, 51169],
 [24, 29, 70995], [3, 22, 3980], [23, 45, 3986], [39, 60, 42595], [5, 53, 55163], [22, 23, 64252], [32, 52, 12351],
 [2, 43, 64520], [57, 60, 37530], [22, 34, 63381], [46, 57, 82870], [28, 36, 15973], [27, 43, 8220], [15, 58, 80791],
 [8, 47, 7858], [19, 50, 80025], [46, 51, 72819], [26, 48, 93610], [29, 54, 51713], [35, 43, 50090], [5, 14, 31054],
 [5, 37, 95577], [23, 51, 76252], [28, 52, 36615], [21, 57, 3048], [22, 30, 24524], [33, 38, 54153], [24, 46, 50166],
 [17, 53, 31749], [44, 45, 10518], [30, 43, 45424], [4, 21, 89025], [11, 24, 70562], [21, 24, 90423], [6, 29, 55580],
 [21, 22, 44534], [20, 29, 89433], [22, 57, 23525], [30, 48, 57103], [3, 9, 32529], [23, 42, 34489], [11, 36, 49910],
 [23, 30, 22176], [11, 58, 3217], [22, 60, 46505], [37, 42, 15269], [2, 51, 80364], [30, 57, 4161], [35, 59, 34647],
 [8, 59, 52948], [31, 49, 60018], [28, 43, 29924], [6, 53, 5703], [14, 22, 83493], [21, 36, 18832], [27, 58, 19379],
 [22, 55, 50396], [7, 57, 75942]]
print(data.minCostToSupplyWater(n, wells, pipes))